public class ArrayQueue implements Queue {

	private static final int DEFAULT_CAPACITY = 10;
	
	Object[] items;
	int front;
	int back;
	int size;
	
	
	public ArrayQueue() {
		init( DEFAULT_CAPACITY );
	}

	
	public ArrayQueue( int capacity ) {
		init( capacity );
	}


	private void init( int capacity ) {
		items = new Object[ capacity ];
		front = 0;
		back = -1;
		size = 0;
	}

	
	public void enqueue( Object x ) {
		if ( size == items.length ) {
			grow();
		}
		back = increment( back );
		items[ back ] = x;
		++size;
	}


	private void grow() {
		Object[] newItems = new Object[ size * 2 + 1 ];
		int idx = front;
		for ( int newIdx = 0; newIdx < size; ++newIdx ) {
			newItems[ newIdx ] = items[ idx ];
			idx = increment( idx );
		}
		items = newItems;
		front = 0;
		back = size - 1;
	}


	private int increment( int idx ) {
		return ( (idx + 1) % items.length );
	}
	

	public Object dequeue() {
		if ( isEmpty() ) {
			throw new IllegalStateException();
		}
		--size;
		Object x = items[ front ];
		items[ front ] = null;
		front = increment( front );
		return x;
	}
	

	public Object first() {
		if ( isEmpty() ) {
			throw new IllegalStateException();
		}
		return items[ front ];
	}
	

	public boolean isEmpty() {
		return ( size == 0 );
	}
	

	public void clear() {
		init( DEFAULT_CAPACITY );
	}

}